package org.example;

import java.util.Arrays;
import java.util.List;

/**
 * 377. 组合总和 Ⅳ
 * 通过 kimi 获取
 */
public class CombinationSum4 {

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1; // 总和为0的组合有一种

        // 从1遍历到target
        for (int i = 1; i <= target; i++) {
            // 遍历数组中的每个数字
            for (int num : nums) {
                // 如果当前数字不大于i，可以更新dp[i]
                if (num <= i) {
                    dp[i] += dp[i - num];
                }
            }
        }

        // dp[target]即为总和为target的组合个数
        return dp[target];
    }

    public static void main(String[] args) {
        String[] s= {"a"};
        String[] s2= new String[]{"a"};
        List<String> a = Arrays.asList("a");
        a.add("b");
        CombinationSum4 solution = new CombinationSum4();
        int[] nums = {1, 2, 3};
        int target = 4;
        System.out.println(solution.combinationSum4(nums, target)); // 输出：7

//        nums = new int[]{1};
//        target = 1;
//        System.out.println(solution.combinationSum4(nums, target));
//
//        nums = new int[]{1, 2};
//        target = 2;
//        System.out.println(solution.combinationSum4(nums, target));

        nums = new int[]{ 2};
        target = 3;
        System.out.println(solution.combinationSum4(nums, target));
    }

//    public int combinationSum4(int[] nums, int target) {
//        int result = 0;
//        int length = nums.length;
//        for (int i = 0; i < length; i++) {
//            if (target % nums[i] == 0) {
//                result++;
//            }
//            if (target % nums[i] > 0) {
//
//            }
//        }
//        return result;
//    }
}
